1. Technical Field of the Invention
The present invention generally relates to classification of Internet Protocol (i.e., “IP”) packets. More particularly, the present invention is directed to a classification support system and method for efficiently classifying fragmented IP packets (i.e., “fragments”) to mitigate the expensive maintenance of state information and buffering of the fragments during conventional classification.
2. Description of the Related Art
Today, computer systems are invariably interconnected into vast computer networks. The interconnected computer systems communicate with each other over packet-switched networks by sending messages. Although many protocols have been developed for transmission of the messages, the preeminent protocol is the Internet Protocol (i.e., “IP”), which subdivides the messages into packets for transmission over the packet-switched networks. Hereinafter, FIG. 1 and FIG. 2 respectively depict conventional IP packet and fragmentation of the IP packet into fragments, while FIG. 3 depicts conventional IP packet classification.
FIG. 1 is a prior art depiction of an Internet protocol (“IP”) packet 100 that illustrates an IP header 101 and a TCP header 103. IP utilizes packets to communicate over packet-switched networks (e.g., the Internet). The packet 100 represents a piece of a message transmitted over the packet-switched networks. The packet 100 comprises an IP header 101, which includes fields 102 . . . 124 and data 107. The data 107 comprises a TCP header 103, which includes fields 126-148, as well data 105. Among other things, the IP header 101 includes a source address 122 and destination address 124 for routing the packet. Packet switching refers to the foregoing protocols that, among other things, divide a message to be sent into packets for transmission. Each packet is individually transmitted and may follow different routes to the destination address. Once all the packets forming the message arrive at the destination, they are assembled into the original message. It should be noted that IP packets are sent without establishment of communication paths or clearing procedures. Thus, there may be no protection against loss, duplication, misdelivery, and the like.
Further with reference to FIG. 1, the IP header 101 includes a plurality of 32-bit words, each of which is subdivided into fields, the description of which will be made in more detail hereafter. The version field 102, which is four bits, indicates a format of the IP header 101. The IHL field 104 (i.e., internal header length), which is four bits, represents the length of the IP header 101 in 32-bit words. It should be noted that the minimum value for a correct IP header 101 is five 32-bit words. It should further be noted that some of the fields in the IP header 101 may be of varying bit sizes. The type of service field 106, which is eight bits, represents abstract parameters for a quality of service (i.e., “QoS”) to guide selection of actual service parameters when transmitting the packet 100 through a particular network over the Internet. The total length field 108, which is 16 bits, represents a total length of the packet 100 in octets (i.e., an octet is 8 bits in length), including both the IP header 101 and data length 107. The identifier field 110, which is 16 bits, represents an identifying value assigned by a sender to aid in assembly of fragments of a packet (i.e., fragment ID). The flags field 112, which is three bits, represents various control flags directed to fragmentation that is described likewise described in greater detail hereinafter. The fragment offset field 114, which is 10 bits, indicates a position of the packet 100 to which a particular fragment belongs. It should be noted that the fragment offset in field 114 is measured in octets, wherein the fragment offset for a first fragment is zero.
Yet further with regard to FIG. 1, the time to live field 116 (i.e., “TTL”), which is 8 bits, indicates a maximum time that the packet 100 is allowed to remain on the Internet. It should be noted that is the value of field 116 is measured in seconds and if it reaches zero, the packet 100 is destroyed. The protocol field 118, which is eight bits, indicates a next level protocol used in the data portion of the packet, such as TCP protocol described herein below. The header checksum field 120, which is 16 bits, represents a checksum only for the IP header 101 of the packet 100. The checksum 120 is a simple error-detection scheme in which the packet 100 is accompanied by a numerical value based on the number of set bits in the IP header 101. It should be noted that since values in various header fields change, the value of field 120 is recomputed and verified at each point where the IP header 101 of packet 100 is processed. The source address field 122 and destination address field 124, which are 32 bits in length, respectively provide the source and destination addresses for the packet 100.
Still further with reference to FIG. 1, the TCP header 101 also includes a plurality of 32-bit words, each of which is subdivided into fields, the description of which will be made in more detail hereafter. The source port field 126, which is 16 bits, indicates a source port. The destination port 128, which is likewise 16 bits, indicates a destination port. In TCP/IP packet-switched networks, the source and destination ports represent endpoint of a logical connection. For example, a port number of 80 is generally used for HTTP (i.e., HyperText Transfer Protocol) traffic. The sequence number field 130 indicates a first data octet in a fragment, except that if SYN is present, the sequence number 220 is ISN+1 (i.e., initial sequence number). The acknowledgement number filed 132, which is 16 bits, is used for error correction and generally contains a value of a next sequence number to be received. The data offset filed 134, which is 4 bits, represents a number of 32-bit words in the TCP header 103. Thus, this number generally indicates where data 105 of packet 100 begins. The reserved field 136, which is 6 bits in length, represents bits reserved for future use and is presently set to zero. The flags field 138, comprises six control bits, including: 1) urgent pointer field significant (i.e., URG); 1) acknowledgement field significant (i.e., ACK); 2) push function (i.e., PSH); 4) reset the connection (i.e., RST); 5) synchronize sequence numbers (i.e., SYN) and 6) no more data from the sender (i.e., FIN). Window field, which is 16 bits, indicates a number of data octets that the sender of this fragment is willing to accept, beginning with the first octet indicated in the acknowledgement number field 130. The TCP checksum field 142, which is 16 bits, is used for error detection. The urgent pointer field 144, which is 16 bits, represents a current value of the urgent pointer as a positive offset from the sequence number field 130 in this fragment. That is, the urgent pointer points to a sequence number of an octet following urgent data and urgent pointer field 146 is interpreted only if the URG control bit is set in field 138. The options field 146 represents available options, may or may not appear in the TCP header and may vary in length. The padding filed 148 appends enough padding to ensure that the TCP header 103 ends on a 32-bit boundary.
FIG. 2 is a prior art high-level depiction 200 of packet fragmentation for packet 100 of FIG. 1. One of the mechanisms of the Internet Protocol (“IP”) routing is fragmentation and reassembly of packets. While being transmitted over the Internet via myriad intermediary packet-switched networks, the contents of packet 100 do not change on the way to its destination unless fragmentation occurs. Every physical network of the Internet has its own limitation on the size of data that it may carry, which is indicated by an associated MTU (i.e., maximum transmission unit). Under some circumstances, particularly when a large packet must travel through a network with a smaller MTU, the packet must be divided into a plurality of smaller fragments at appropriate places 202 (i.e., fragments are also packets) within the smaller MTU, such as fragment 201 and fragment 203, so that the fragments may travel through the network onto their journey to the destination. This process of division is called fragmentation. Every fragment 201 and 203 includes an IP header HD-I 204 and HD-II 210, and each of which respectively carries data 208 and 212 that is part of data 105 of the original packet 100. It should be noted that during fragmentation, only a sequentially first fragment 201 includes a TCP header 206, which is obtained from the TCP header 103 of packet 100.
A conventional IP packet classifier utilizes the data in the IP header 101 and TCP header 103 to classify the arriving IP packets including IP fragments, i.e., TCP classification. The conventional packet classifier classifies the arriving IP packets (and fragments) into flows based on a set of rules in a rules database maintained by the packet classifier, wherein each flow obeys at least one of the set of rules. The classifier consults the rules database for each arriving packet. In particular, the rules database has a set of pattern and action associations. In the case of TCP rules, the pattern usually includes fields from the IP 101 and TCP 103 headers, as particularly illustrated in FIG. 1 above. The pattern may be either an exact match on a field value or on a range of values in the headers 101 and 103. During classification, a key is extracted from the arriving packet or fragment. Generally, the key is formed by taking fields from the IP 101 and TCP 103 headers (depicted in FIG. 1 above). The classifier will then, using a classification algorithm (not important here), find the best match of the extracted key to a pattern in the rules database. The classifier will then apply the actions found in the rules database corresponding to the matching pattern. The possible actions may include discarding the packet (i.e., destroying it); forwarding the packet (i.e., normal processing); updating the type of service field (i.e., “ToS”) 106 depicted in FIG. 1 for the packet; directing the packet to an alternate next router (i.e., overriding the next router as determined by a conventional IP routing algorithm); directing the packet to a MultiProtocol Label Switching (i.e., “MPLS”) network; redirecting the packet to another processor for more advanced packet processing, and policing a rate of packets of a particular flow (i.e., if the rate is exceeded, discarding the packets).
In the case of IP fragments, the key cannot be extracted directly from the fragments, since only a sequentially first fragment includes all of the necessary information, i.e., a TCP header 103 of FIG. 1. As a consequence, for such packets, the classification must be enhanced. More particularly, since the information in the TCP header 103, such as source port 126 and destination port 128, is included in the sequentially first fragment 201 and it is often part of classification rules for IP fragments in the conventional classifier, state information must necessarily be maintained for the fragmented packet during the time that the IP fragments for the fragmented packet are processed via the classifier. Furthermore, buffering of the IP fragments may be required since the IP fragments may arrive out of sequence, i.e., sequentially first IP fragment may not arrive first. Consequently, the storage of state information and the buffering of IP fragments are computationally expensive. Furthermore, the classification of the IP fragments via the conventional classifier described with reference to FIG. 3 below cannot be performed on a “wire speed” forwarding platforms, such as International Business Machines (i.e., “IBM”) Network Processor (i.e., high-speed hardware-based forwarding platform depicted in FIG. 9) and must necessarily be redirected to slow path forwarding platforms, such as Control Point (i.e., depicted in FIG. 10). Consequently, the conventional classifiers are not practical for high-speed hardware-based forwarding platforms, where speed is essential.
FIG. 3 depicts a method flowchart 300 for a conventional IP packet classifier. Before, the prior art classification is described, it is should be noted that there exists a fragment database, which associates a particular pattern to a list of fragments to which actions must be applied. More particularly, the pattern for the fragment database includes the source address 122 and a fragment ID 110 from IP header 101 depicted in FIG. 1 above. Conventional classification starts at step 302. At step 304, the classifier receives an IP packet. At step 306, the classifier determines whether the received IP packet is a fragment of a fragmented IP packet. Referring to FIG. 1, determination of whether the received packet is fragmented may be accomplished by a two-field test, i.e., testing a more fragments flag that is part of flags field 112 in FIG. 1 and testing the fragment offset field 114 of FIG. 1. The more fragments flag being equal to zero indicates that there has been no fragmentation, whereas the more fragments flag not being equal to zero indicates that the received IP packet is a fragment in most instances. Since a sequentially last fragment of a fragmented packet will have the more fragments flag equal to zero, the second test must also be performed. If the fragment offset 114 is not equal to zero, then the packet is a fragment, i.e., a sequentially last fragment. Now referring back to FIG. 3, if the received packet is not fragmented, normal IP packet classification is performed at step 308, as particularly described above with reference to classification of IP packets above. However, if the received packet is a fragment as determined at step 306, and then the source address 122 and fragment ID 110 are extracted from the IP header 101 of the fragment, which is illustratively depicted in FIG. 1. At step 312, it is determined whether the fragment is a sequentially first fragment of the fragment IP packet. Again referring to FIG. 1, the fragment offset field 114 of IP header 101 indicates a position of the fragment in the fragmented IP packet. Consequently, if the fragment offset field 114 contains a value of zero, this represents that the fragment is a sequentially first fragment. If it is determined at step 312 that the fragment is not a sequentially first fragment, processing continues to step 314 where using the extracted source address 122 and fragment ID 110 as part of a key, the classifier performs a look up at step 316 to obtain an action to be performed on the fragment. If the key is not found, then no actions were yet ascribed to the fragmented IP packet of which the fragment is part, and the fragment is buffered with its key (source address and fragment ID) at step 318. However, if step 316 the key if found for the fragment, an action pursuant to this key is applied at step 320 to the fragment and the method exits at step 332. It is noted, that in instances where although the key is found at step 316 no actions are ascribed, the packet is buffered together with a list of buffered fragments according to a particular pattern associated with the fragment. Thereafter, the method exists at step 322.
Now returning back to step 312, if it determined that the fragment is a sequentially first fragment of the fragmented IP packet, then at step 322 TCP classification is performed as described above. That is, a key is extracted from the received sequentially first fragment and matched to a pattern in the rules database, thereby obtaining actions associated with the matched pattern. At step 324, the actions are stored in the fragmentation database using the source address 122 and fragment ID 110 of the sequentially first fragment as a key so that the actions may later be applied to other fragments. More particularly, the actions are copied from the rules database to the fragmentation database. At step 326, a lookup for all fragments that were buffered at step 318 is performed utilizing the key (source address and fragment ID). At step 328, a determination is made regarding whether there is another buffered fragment for the fragmented IP packet by utilizing the key. At step 330, an action associated with the key is applied to the buffered fragment and the fragment is released. Once all buffered fragment have been processed, at step 320 the sequentially first fragment is processed utilizing the actions associated with the key and the method exits at step 332. It should be noted, however, that the sequentially first fragment may be processed before all buffered fragments depending upon implementation. That is, normally a router does not re-order received fragments into their sequential order because it may be too expensive, but reordering may save processing time in subsequent routers.
The conventional classification of fragmented packets described above is not practical for implementation in a system, which utilizes high-speed forwarding devices, such as network processors (i.e., “NPs”). The NPs often have a limited number of instructions that can be executed per packet in order to maintain “wire-speed” forwarding rates for the received fragments. The above-identified algorithm, when implemented as a program, is likely to exceed a maximum number of instructions allowed for wire speed forwarding in an NP. Furthermore, the required buffering of fragments, maintenance of state information and lists of packets in the fragment database may be beyond the capability of the NP. As a consequence, the fragments may be forwarded for processing to a general-purpose processor. Since the general-purpose processor is orders of magnitude slower than the NP, wire speed forwarding of fragmented packets (i.e., fragments) cannot be achieved.
In view of the above described prior art classification there is a need in the art to provide a classification support system and method to robustly and efficiently classify IP fragments, mitigating the expensive maintenance of state information and buffering of IP fragments necessitated during conventional classification, thereby allowing the classification to be performed on the wire-speed network processors.